package org.dubh.problems;

/**
 * Search in a list that is sorted, but rotated at some unknown pivot point
 * in O(lgn).
 */
public final class RotatedListSearch {
    private RotatedListSearch() {
    }
    
    public static int searchRotatedList( int[] a, int search ) {
        if ( a.length == 0 ) return -1;
        if ( a.length == 1 ) return a[0] == search ? 0 : -1;
        
        int pivot = findPivot( a, 0, a.length - 1 );
        
        if ( a[0] <= search && a[pivot] >= search ) return binarySearch( a, 0, pivot, search );
        return binarySearch( a, pivot, a.length-1, search );
    }
    
    private static int binarySearch( int[] a, int start, int end, int search ) {
        if ( end == start ) return a[start] == search ? start : -1;
        
        int mid = start + ((end-start)/2);
        int midval = a[mid];
        if ( midval > search ) return binarySearch( a, start, mid-1, search );
        return binarySearch( a, mid+1, end, search );
    }
    
    private static int findPivot( int[] a, int start, int end ) {
        if ( end == start ) return start;
        
        int mid = start + ((end-start)/2);
        if ( a[start] > a[mid] ) return findPivot( a, start, mid );
        if ( a[mid+1] > a[end] ) return findPivot( a, start+mid+1, end );
        
        return mid;
    }
}
